package com.leetcode.Offer;

import java.util.Stack;

public class JZ31 {
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        //定义一个栈，向里面不断添加pushed元素，出现和popped相同的元素就弹出，最后判断指针是否在末端
        if (pushed==null&&popped==null){
            return true;
        }

        Stack<Integer> stack = new Stack<>();
        int a = 0;//push
        int b = 0;//pop
        while (a < pushed.length) {
            if (stack.isEmpty() || stack.peek() != popped[b]) {
                stack.push(pushed[a]);
                a++;
            }
            while (!stack.isEmpty() && stack.peek() == popped[b]) {
                stack.pop();
                b++;
            }
        }
        if (stack.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        System.out.println(new JZ31().validateStackSequences(new int[]{1, 2, 3, 4, 5}, new int[]{4,3,5,1,2}));
    }
}
